﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/intersection-of-two-arrays/
/*
题目描述：
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
*/

// 方法1——去重后再遍历
/*
思路：
对两个数组进行去重后再对两个数组进行双层遍历，
遍历nums1的每个元素，对于每个元素，都在nums2中寻找，看看它在nums2中是否存在，
若存在，则存入一个返回数组。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
// 先写一个函数，比较两个整数的大小
int cmp_int(const void* p1, const void* p2) {
	assert(p1 && p2);
	return *((int*)p1) - *((int*)p2);
}
// 写一个函数，用双指针的思路对一个数组进行去重,并返回去重后数组的长度
int Deduplication(int* nums, int numsLen) {
	assert(nums);
	// 先对数组进行排序
	qsort(nums, numsLen, sizeof(nums[0]), cmp_int);
	int cur = 0;
	int give = 0;
	for (cur = 1; cur < numsLen; cur++) {
		if (nums[cur] != nums[give]) {
			nums[give + 1] = nums[cur];
			give++;
		}
	}
	return give + 1;
}

int* intersection1(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
	assert(nums1 && nums2);
	// 先对nums1和nums2进行去重
	nums1Size = Deduplication(nums1, nums1Size);
	nums2Size = Deduplication(nums2, nums2Size);
	int* ans = (int*)malloc(nums1Size * sizeof(int));
	if (NULL == ans) {
		perror("intersection");
		return NULL;
	}
	int target = 0;
	int j = 0;
	int n = 0;
	for (target = 0; target < nums1Size; target++) {
		for (j = 0; j < nums2Size; j++) {
			if (nums2[j] == nums1[target]) {
				ans[n] = nums1[target];
				n++;
				break;
			}
		}
	}
	*returnSize = n;
	return ans;
}
// 时间复杂度：O(mn)，m和n分别为两个数组的元素个数。对两个数组进行排序的时间复杂度分别为O(mlogm)和O(nlogn)，
// 去重的时间复杂度分别为O(m)和O(n)。最后循环的时间复杂度为O(mn)，故总的时间按复杂度为O(mn)。
// 空间复杂度：O(logm + logn)，m和n分别是两个数组的元素个数，空间复杂度主要取决于对两个数组进行排序时所使用的额外空间。


int main() {
	int arr1[] = { 1, 2, 2, 1 };
	int arr2[] = { 2, 2 };
	int len1 = sizeof(arr1) / sizeof(arr1[0]);
	int len2 = sizeof(arr2) / sizeof(arr2[0]);
	int len3 = 0;
	int* returnLen = &len3;
	int* array = intersection(arr1, len1, arr2, len2, returnLen);
	int i = 0;
	for (i = 0; i < len3; i++) {
		printf("%d ", array[i]);
	}
	return 0;
}


// 方法2——排序后双指针
/*
思路：
对两个数组进行升序排序之后，就可以使用双指针的方法求得两个数组的交集，具体步骤如下：
首先我们让两个指针p1和p2分别指向nums1和nums2的第一个元素；
如果p1和p2所指向的元素不相等，则应该让指向元素较小的指针向右移动一位；
我们需要用一个变量pre来记录前一个加入答案数组的元素，如果p1和p2所指向的元素相等且不等于pre则将该元素写入答案数组，
并将pre更新为该元素，然后p1和p2都向右边移动一位。如果只是p1和p2所指向的元素相等但却等于pre，
则只让p1和p2都向右移动一位。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int* intersection2(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
	assert(nums1 && nums2);
	// 先对两个数组进行排序
	qsort(nums1, nums1Size, sizeof(nums1[0]), cmp_int);
	qsort(nums2, nums2Size, sizeof(nums2[0]), cmp_int);
	int* ans = (int*)malloc(nums1Size * sizeof(nums1[0]));
	if (NULL == ans) {
		perror("intersection2");
		return NULL;
	}
	int n = 0;
	int pre = -1;
	int p1 = 0;
	int p2 = 0;
	while ((p1 < nums1Size) && (p2 < nums2Size)) {
		if (nums1[p1] < nums2[p2]) {
			p1++;
		}
		else if (nums2[p2] < nums1[p1]) {
			p2++;
		}
		else {
			if (nums1[p1] != pre) {
				ans[n] = nums1[p1];
				n++;
				pre = nums1[p1];
				p1++;
				p2++;
			}
			else {
				p1++;
				p2++;
			}
		}
	}
	*returnSize = n;
	return ans;
}
// 时间复杂度：O(mlogm+ nlogn)，m和n分别为两个数组的元素个数，对两个数组进行排序的时间复杂度分别是O(mlogm)和O(nlogn)，
// 双指针求交集的时间复杂度为O(m + n)，故总时间复杂度为O(mlogm + nlogn)。
// 空间复杂度：O(logm + logn)，m和n分别为两个数组的元素个数，空间复杂度主要取决于排序所使用的额外空间。
